package com.cat.enumerate;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/largest-time-for-given-digits/?envType=problem-list-v2&envId=enumeration
 * @create 2025/9/20 18:57
 * @since JDK17
 */

public class Solution02 {
    int min = -1, sec = -1;
    boolean[] h = new boolean[4];
    int[] arr;
    void dfs(int cur, int m, int s) {
        if (m > 23 || s > 59) { // 不合法
            return;
        }
        if (cur == 4) {
            int n1 = m * 60 + s, n2 = min * 60 + sec;
            if (n1 > n2) {
                min = m;
                sec = s;
            }
            // System.out.println("hehe" + m + " " + s);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (!h[i]) {
                h[i] = true;
                if (cur < 2) {
                    dfs(cur + 1, m * 10 + arr[i], s);
                } else {
                    dfs(cur + 1, m, s * 10 + arr[i]);
                }
                h[i] = false;
            }
        }
    }

    public String largestTimeFromDigits(int[] arr) {
        this.arr = arr;
        dfs(0, 0, 0);
        String m = Integer.valueOf(min).toString();
        String s = Integer.valueOf(sec).toString();
        if (min < 10) {
            m = "0" + m;
        }
        if (sec < 10) {
            s = "0" + s;
        }

        return min == -1 ? "" : m + ":" + s;
    }
}
